package Implementaciones;

/**
 * Universidad del Valle de Guatemala
 * Algoritmos y Estructura de Datos
 * @author Juan Pablo Argueta, 11033
 * 13 de noviembre del 2012
 */

import Grafos.*;
import java.util.Iterator;

//----------------------------------------------------------------------------
// Clase de referencia de:
//
// Bailey, A. 2007. Java Structures: Data Structures for the 
//      Principled Programmer. Williams College.
//----------------------------------------------------------------------------

/**
 *
 * @author Juan Pablo
 * @param <V>
 * @param <E>
 */
public class Floyd <V,E> {

    //------------------------------------------------------------------------
    // Atributos
    //------------------------------------------------------------------------
    //Grafo original.
    private Graph graphW, g;
    //Grafo compuesto después del algoritmo.
    private Graph graphD;
    //Matriz de posiciones
    private Object positions [][];
    
    int min[];
    int max[];
    int centroGrafo;
    
    //------------------------------------------------------------------------
    // Constructor
    //------------------------------------------------------------------------
    
    /**
     * Construye el algoritmo de Floyd.
     * @pre: Se debe ingresar el grafo.
     * @post: Se construye un grafo con el algoritmo.
     * @param graphW 
     */
    public Floyd(Graph graphW) {
        this.graphW = graphW;
        this.graphD = graphW;
        this.positions = new Object [graphW.size()][graphW.size()];
        algorithm(graphD);
    }
   
    //------------------------------------------------------------------------
    // Getters y Setters
    //------------------------------------------------------------------------

    /**
     *
     * @return
     */
    public Graph getGraphW() {
        return graphW;
    }

    /**
     *
     * @param graphW
     */
    public void setGraphW(Graph graphW) {
        this.graphW = graphW;
    }

    /**
     *
     * @return
     */
    public Graph getGraphD() {
        return graphD;
    }

    /**
     *
     * @param graphD
     */
    public void setGraphD(Graph graphD) {
        this.graphD = graphD;
    }

    /**
     *
     * @return
     */
    public Object[][] getPositions() {
        return positions;
    }

    /**
     *
     * @param positions
     */
    public void setPositions(Object[][] positions) {
        this.positions = positions;
    }
    
    //------------------------------------------------------------------------
    // Métodos
    //------------------------------------------------------------------------
   
    /**
     * Método que realiza el algoritmo de Floyd.
     * @pre: -
     * @post: El grafo graphD se queda con la nueva información creada en el 
     * algoritmo.
     * @param g 
     */
    public void algorithm(Graph g){
       //Contadores para las posiciones de la matriz de posiciones.
       int contu = 0;
       int contv = 0;
       //Se llena la matriz de posiciones con posiciones vacias.
       for (int x=0; x<positions.length; x++){
           for (int y=0; y<positions.length; y++){
               positions[x][y] = "";
           }
       }
       
       //Se comienza iterando el grafo.
       Iterator <V> writer = graphD.iterator();
       while (writer.hasNext()){
           Iterator <V> uniter = graphD.iterator();
           V w = writer.next();
           while (uniter.hasNext()){ 
               Iterator <V> viter = graphD.iterator();
               V u = uniter.next();
               while (viter.hasNext())
               {
                   //Vericación del camino más corto y la existencia de ese
                   //camino.
                   V v = viter.next();
                   if (graphD.containsEdge(u, w) && graphD.containsEdge(w, v)){
                       Edge<V,E> leg1 = graphD.getEdge(u,w); 
                       Edge<V,E> leg2 = graphD.getEdge(w,v);
                       double leg1Dist = (Double) leg1.label();
                       double leg2Dist = (Double) leg2.label();
                       double newDist = leg1Dist + leg2Dist;
                       
                       if (graphD.containsEdge(u,v)){
                           Edge<V,E> across = graphD.getEdge(u,v);
                           double acrossDist = (Double) across.label();
                           if (newDist < acrossDist){
                               //Se agrega el camino más corto.
                               graphD.addEdge(u, v, newDist);
                               //Se guarda en la matriz de posiciones.
                               positions[contu][contv]=w.toString();
                           }
                       }else{
                           //Verificación de que no se quiera ir al mismo nodo.
                           if(u.equals(v)==false){
                                //Se agrega el camino más corto.
                                graphD.addEdge(u, v, newDist);
                                //Se guarda en la matriz de posiciones.
                                positions[contu][contv]=w.toString();
                           }
                       }
                   }
                   contv++;
               }
           contv=0;
           contu++;
           }
       contu=0;
       }
   }
   
   
   //public 
}
